package graph.tree;

import graph.weight.Edge;
import graph.weight.EdgeWeightedGraph;
import linear.Queue;
import priority.MinPriorityQueue;
import uf.UF_Tree_Weighted;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * kruskal 算法 最小生成树
 */
public class KruskalMST {
    /**
     * 最小生成树的所有边
     */
    private Queue<Edge> mst;
    /**
     * 并查集 存储所有顶点 并体现出 顶点与顶点之间最小边生成情况 用于判断某条边是否可以作为最小边
     * 思路：
     * 1. 将所有边存入pq 每次delMin 取出最小边
     * 2. 利用uf 判断当前边涉及顶点是否已经被 最小边连接 如果有 则该边不是最小边 否则 uf 连接对应顶点 并且记录当前边为最小边
     */
    private UF_Tree_Weighted uf;
    /**
     * 存储所有边，按照权重排序
     */
    private MinPriorityQueue<Edge> pq;

    public KruskalMST(EdgeWeightedGraph G) {
        mst = new Queue<>();
        uf = new UF_Tree_Weighted(G.V());
        pq = new MinPriorityQueue<>(G.E() + 1);

        for (Edge e : G.edges()) {
            pq.insert(e);
        }

        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge minEdge = pq.delMin();
            int v = minEdge.either();
            int w = minEdge.other(v);
            if (uf.connected(v, w)) {
                continue;
            }
            uf.union(v, w);
            mst.enqueue(minEdge);
        }
    }

    //获取最小生成树的所有边
    public Queue<Edge> edges() {
        return mst;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new
                InputStreamReader(PrimMST.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt")));
        //读取顶点数目，初始化EdgeWeightedGraph图
        int number = Integer.parseInt(reader.readLine());
        EdgeWeightedGraph G = new EdgeWeightedGraph(number);
        //读取边的数目
        int edgeNumber = Integer.parseInt(reader.readLine());
        //循环读取每一条边，并调用addEdge方法
        for (int i = 0; i < edgeNumber; i++) {
            String line = reader.readLine();
            int v = Integer.parseInt(line.split(" ")[0]);
            int w = Integer.parseInt(line.split(" ")[1]);
            double weight = Double.parseDouble(line.split(" ")[2]);
            G.addEdge(new Edge(v, w, weight));
        }

        //构建PrimMST对象
        KruskalMST mst = new KruskalMST(G);
        //获取最小生成树的边
        Queue<Edge> edges = mst.edges();
        //打印输出

        for (Edge e : edges) {
            System.out.println(e.either() + "-" + e.other(e.either()) + "::" + e.weight());
        }

    }
}
